package glossos.tree;

import glossos.search.LRUCache;
import java.util.Stack;

/**
 * A stack for {@link Node} objects, satisfying the following relation for any two objects {@code a} and {@code b},
 * referring to instances of {@link Node}:
 *<p>  
 * {@code a} is parent of {@code b} <=> {@code a} is on top of {@code b} in the stack.
 * </p>
 * @author Otavio Macedo
 *
 */
class NodeStack {
    private final Stack<String> wordStack;
    private static final LRUCache<Node, NodeStack> STACK_CACHE = new LRUCache<Node, NodeStack>(40);

    /**
     * Constructs a node stack defining both the bottom and top nodes;
     * @param bottomNode the node that is to be at the bottom of the stack. Cannot be a root node.
     * @param topNode defines a boundary for pushing nodes into the stack.
     * The stack will contain all nodes in the parent chain, from the bottom
     * node up to a children of this node.
     * <p>
     * This implementation assumes that the tree to which the nodes belong is single rooted. 
     * </p>
     */
    public static NodeStack forNodes(Node bottomNode, Node topNode) {
        return new NodeStack(bottomNode, topNode);
    }

    public static NodeStack forNode(Node bottomNode){
        if (!STACK_CACHE.contains(bottomNode)){
            NodeStack nodeStack = new NodeStack(bottomNode, null);
            STACK_CACHE.put(bottomNode, nodeStack);
            return nodeStack;
        }
        return STACK_CACHE.get(bottomNode);
    }

    private NodeStack(Node bottomNode, Node topNode) {
        Node node = bottomNode;
        wordStack = new Stack<String>();
        while (canIncludeWord(node, topNode)) {
            wordStack.push(node.getWord());
            node = node.getParent();
        }
    }

    private boolean canIncludeWord(Node node, Node stopNode) {
        return !node.equals(stopNode) && !node.isRoot();
    }

    /**
     * Returns a String built up from the node words, from top to bottom.
     */
    @Override
    public String toString() {
        StringBuilder result = new StringBuilder(wordStack.pop());
        while (!wordStack.empty()) {
            result.append(" ").append(wordStack.pop());
        }
        return result.toString();
    }
}
